package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/10/27.
 */

/*
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

        According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N ? h papers have no more than h citations each."

        For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

        Note: If there are several possible values for h, the maximum one is taken as the h-index.

*/

public class N274_H_Index {
    public static void test(){

        int[] data=new int[]{0,1};
        System.out.println(new N274_H_Index().hIndex(data));
        System.out.println(new N274_H_Index().hIndex2(data));
    }

    public int hIndex(int[] citations) {
        if(citations==null||citations.length==0){
            return 0;
        }

        int[] count=new int[citations.length+1];
        for(int i=0;i<citations.length;++i){
            if(citations[i]>=citations.length){
                count[citations.length]++;
            }else{
                count[citations[i]]++;
            }
        }

        if(count[citations.length]>=citations.length){
            return citations.length;
        }

        for(int i=citations.length-1;i>=0;--i){
            count[i]+=count[i+1];
            if(count[i]>=i){
                return i;
            }
        }

        return 0;
    }

    /*Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
    */
    public int hIndex2(int[] citations) {
        if(citations==null||citations.length==0){
            return 0;
        }


        int left=0,right=citations.length-1;
        while (left<=right){
            int mid=(right+left)/2;
            int count=citations.length-mid;
            if(count==citations[mid]){
                return citations.length-mid;
            }else if(count>citations[mid]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }

        return citations.length-left;
    }
}
